package site.wanjiahao;

import java.util.Iterator;

public class ArrayList<E> implements List<E>, Iterable<E> {

    private int size = 0;

    private Object[] elements;

    private static final int DEFAULT_CAPACITY = 10;

    private static final int NOT_FOUND_ELEMENT = -1;

    public ArrayList() {
        this(DEFAULT_CAPACITY);
    }

    public ArrayList(int capacity) {
        if (capacity <= DEFAULT_CAPACITY) {
            capacity = DEFAULT_CAPACITY;
        }
        elements = new Object[capacity];
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean contains(E ele) {
        return indexOf(ele) != NOT_FOUND_ELEMENT;
    }

    @Override
    public void add(E ele) {
        // 添加元素至线性表头部
        add(size, ele);
    }

    @Override
    public E get(int index) {
        rangeCheck(index);
        return (E) elements[index];
    }

    @Override
    public E set(int index, E ele) {
        rangeCheck(index);
        E old = (E) elements[index];
        elements[index] = ele;
        return old;
    }

    @Override
    public void add(int index, E ele) {
        // 判断添加索引是否合法
        rangeCheckForAdd(index);
        // 确保线性表容量足够
        ensureCapacity();
        // 判断是否在队尾添加元素
        if (index == size) {
            elements[size++] = ele;
            return;
        }
        if (size - index >= 0)
            System.arraycopy(elements, index, elements, index + 1, size - index);
        elements[index] = ele;
        size++;
    }

    @Override
    public E remove(int index) {
        rangeCheck(index);
        // 直接覆盖法
        E old = (E) elements[index];
        if (size + 1 - index >= 0)
            System.arraycopy(elements, index + 1, elements, index, size + 1 - index);
        // 释放指向内存
        elements[--size] = null;
        return old;
    }

    @Override
    public int indexOf(E ele) {
        // 使用equals方法比较，比较判断条件扩展性高，而不是直接比较内存地址
        if (ele != null) {
            for (int i = 0; i < size; i++) {
                if (ele.equals(elements[i])) {
                    return i;
                }
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (null == elements[i]) {
                    return i;
                }
            }
        }
        return NOT_FOUND_ELEMENT;
    }

    @Override
    public void clear() {
        for (int i = 0; i < size; i++) {
            // 释放内存数据
            elements[i] = null;
        }
        size = 0;
    }

    @Override
    public String toString() {
        int end = size - 1;
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(elements[i]);
            if (i != end) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }

    @Override
    public Iterator<E> iterator() {
        return new Iter();
    }

    /**
     * 迭代器接口
     */
    private class Iter implements Iterator<E> {

        private int point;

        @Override
        public boolean hasNext() {
            return point != size;
        }

        @Override
        public E next() {
            return get(point++);
        }
    }

    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > size) {
            // 不合法
            outOfBound(index);
        }
    }

    private void rangeCheck(int index) {
        if (index < 0 || index >= size) {
            // 不合法
            outOfBound(index);
        }
    }

    private void outOfBound(int index) {
        throw new ArrayIndexOutOfBoundsException("size: " + size + ", index: " + index);
    }

    private void ensureCapacity() {
        int capacity = size + 1;
        int oldCapacity = elements.length;
        // 判断容量是否足够
        if (capacity >= oldCapacity) {
            // 增加1.5倍容量
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            Object[] newAry = new Object[newCapacity];
            // 拷贝数组
            if (size >= 0) System.arraycopy(elements, 0, newAry, 0, size);
            elements = newAry;
        }
    }

}
